package com.tgy.divide_conquer;

import java.util.Objects;

/**
 * @Author: tgy
 * @Date: 2020/11/4 8:35 下午
 */
public class MaxSubArray {

    private int[] nums;

    public int maxSubArray(int[] nums) {

        if (Objects.isNull(nums) || nums.length == 0) {

            return 0;
        }

        if (nums.length == 1) {

            return nums[0];
        }

        this.nums = nums;
       return findMaxSubArray(0,nums.length);
    }

    private int findMaxSubArray(int begin, int end) {

        if (end - begin == 1) {

            return nums[begin];
        }

        int mid = (begin + end) >> 1;

        int maxDouble = Math.max(findMaxSubArray(begin,mid),findMaxSubArray(mid,end));

        int leftMax = Integer.MIN_VALUE,sum = 0;

        for (int i = mid - 1; i >= begin ; i--) {

            sum += nums[i];
            if (leftMax < sum) {

                leftMax = sum;
            }
        }

        int rightMax = Integer.MIN_VALUE;
        sum = 0;

        for (int i = mid; i < end; i++) {

            sum += nums[i];
            if (rightMax < sum) {

                rightMax = sum;
            }
        }

        return Math.max(leftMax + rightMax,maxDouble);
    }
}
